package July.SplitArray;

//410. 分割数组的最大值
public class Split {

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] a = new int[] {
            7,
            2,
            5,
            10,
            8
        };
        s.splitArray(a, 2);
    }
}

//dp
class Solution_DP {
    public int splitArray(int[] nums, int m) {
        int n = nums.length;
        int[] preSum = new int[n];
        preSum[0] = nums[0];
        for (int i = 1; i < n; i++) {
            preSum[i] = preSum[i - 1] + nums[i];
        }
        int[][] dp = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (j != 0) {
                    int minPre = Integer.MAX_VALUE;
                    for (int k = 0; k < i; k++) {
                        minPre = Math.min(Math.max(preSum[i] - preSum[k], dp[k][j - 1]), minPre);
                    }
                    dp[i][j] = minPre;
                } else {
                    dp[i][j] = preSum[i];
                }
            }
        }
        return dp[n - 1][m - 1];
    }
}

//求最大值的最小值 ----> 折办查找
class Solution {
    public int splitArray(int[] nums, int m) {
        /**
         *返回值只可能在 nums的最大值和 nums的和之间
         因此这般查找
         */
        int left = 0;
        int right = 0;
        for (int i: nums) {
            left = left > i ? left : i;
            right += i;
        }

        while (left < right) {
            int mid = left + (right - left) / 2;
            int cnt = 1; //表示当前的数组划分数量
            int tmp = 0;
            for (int i: nums) {
                tmp += i;
                if (tmp > mid) {
                    tmp = i;
                    cnt++;
                }
            }
            // if(cnt==m) return mid; //不能直接返回,划分的数目一样,但是值可能偏大,所以等于的时候
                                        //应该让high = mid 看看能不能找到更小的
            if (cnt > m)
                left = mid + 1;
            else right = mid;
        }
        return left;
    }
}